#include<iostream>
using namespace std;

template<class T>
class MaxHeap{
private:
    T* heapArray;
    int CurrentSize;
    int MaxSize;
public:
    MaxHeap(T* array,int num,int max);
    virtual ~MaxHeap(){}
    void buildHeap();
    bool isLeaf(int pos) const;
    int leftChild(int pos) const;
    int rightChild(int pos) const;
    int parent(int pos) const;
    void SiftDown(int left);
    void SiftUp(int position);
    bool Insert(constT& newNode);
    void MoveMax();
    bool Remove(int pos,T& node);
    T& RemoveMax();
};



template<class T>
void MaxHeap<T>::buildHeap(){
    for(int i = CurrentSize/2-1;i>=0;i--)
        SiftDown(i);
}



template<class T>
void MaxHeap<T>::SiftDown(int left){
    int i = left;
    int j = 2*i+1;
    T temp = heapArray[i];

    while(j<CurrentSize){
        if((j<CurrentSize-1)&&(heapArray[i]<heapArray[i+1]))
            j++;
        if(temp<heapArray[j]){
            heapArray[i]=heapArray[j];
            i=j;
            j=2*j+1;
        }
        else break;
    }
    heapArray[i]=temp;
}
